package code;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class Candy {
	
	public int candy(int[] ratings) {
		int ans=0;
		int n=ratings.length;
		int[] num=new int[n];
		int i,j;
		ans=n;
		while(true){
			if(isOk(ratings,num))	
				break;
			for(i=1;i<n;i++){
				if(ratings[i]>ratings[i-1]){
					for(j=i;j<n;j++){
						if(ratings[j]>ratings[j-1] && num[j]<=num[j-1]){
							num[j]=num[j-1]+1;
							continue;
						}
						break;
					}
				}
				else if(ratings[i]<ratings[i-1]){
					for(j=i;j<n;j++){
						if(ratings[j]<ratings[j-1] && num[j]>=num[j-1]){
							continue;
						}
						break;
					}
					for(j--;j>=i;j--){
						num[j-1]=num[j]+1;
					}
				}
			}
		}
		for(i=0;i<n;i++){
			ans+=num[i];
		}
        return ans;
    }
	
	public boolean isOk(int[] ratings,int num[]){
		int n=ratings.length;
		for(int i=0;i<n-1;i++){
			if(ratings[i]>ratings[i+1] && num[i]<=num[i+1])	
				return false;
			if(ratings[i]<ratings[i+1] && num[i]>=num[i+1])
				return false;
		}
		return true;
	}
	
	static class UndirectedGraphNode {
		    int label;
		    List<UndirectedGraphNode> neighbors;
		    UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
	}
	
	public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
		Map<UndirectedGraphNode,UndirectedGraphNode> map=new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
		Set<UndirectedGraphNode> vis=new HashSet<UndirectedGraphNode>();
		
		UndirectedGraphNode p=node,q;
		UndirectedGraphNode clonedNode=null;
		Stack<UndirectedGraphNode> stack=new Stack<UndirectedGraphNode>();
		stack.add(node);
		
		while(!stack.isEmpty()){
			p=stack.pop();
			if(vis.contains(p))	
				continue;
			vis.add(p);
			if(map.containsKey(p)){
				q=map.get(p);
			}
			else{
				q=new UndirectedGraphNode(p.label);
				map.put(p, q);
			}
			
			if(clonedNode==null)
				clonedNode=q;
			if(p.neighbors!=null){
				List<UndirectedGraphNode> list=new ArrayList<UndirectedGraphNode>();
				for(int i=0;i<p.neighbors.size();i++){
					UndirectedGraphNode cc;
					if(map.containsKey(p.neighbors.get(i))){
						cc=map.get(p.neighbors.get(i));
						list.add(cc);
					}
					else{
						cc=new UndirectedGraphNode(p.neighbors.get(i).label);
						list.add(cc);
						map.put(p.neighbors.get(i), cc);
					}
					/*
					 *�����Ľ�㣬����Ҫ�ټ���stack 
					 */
					if(!vis.contains(p.neighbors.get(i)))
						stack.push(p.neighbors.get(i));
				}
				q.neighbors=list;
			}
		}
		
        return clonedNode;
    }
	public int minCut(String s) {
		
		StringBuilder sb=new StringBuilder();
		int n=s.length();
		int i,j;
		for(i=0;i<s.length();i++){
			sb.append("#");
			sb.append(s.charAt(i));
		}
		sb.append("#");
		String ss=sb.toString();
		int N=2*n+1;
		int[] p=new int[N];
		/*
		 * mx��ʾ��ǰ���ĳ�������ַ��±�
		 * index��ʾ�ַ���ʱ�����Ľ��
		 * i,j�ǹ���index�ԳƵĽ��
		 * i+j=2*index
		 * 
		 */
		
		int mx=0;
		int index=0;
		p[0]=1;
		int cnt=0;
		for(i=1;i<N;i++){
			/*
			 * 2*index-i��i����index�ԳƵĽ��
			 * ��Ϊ��i>index�������ҵ���ĶԳƵ㣬2*index-i,��ʱp[2*index-i]���Ѿ��������Ļ�����ģ���������
			 * mx-i���볤��Ϊp[2*index-i]��ߵĴ���С��0
			 */
			if(mx>i){
				p[i]=mx-i>p[2*index-i]?p[2*index-i]:mx-i;
			}
			else{
				p[i]=1;
			}
			for(;i+p[i]<N && i-p[i]>=0 && ss.charAt(i+p[i])==ss.charAt(i-p[i]);p[i]++);
			
			if(p[i]+i>mx){
				mx=p[i]+i;
				index=i;
			}
		}
		int ans=0;
		int[] dp=new int[N];
		dp[0]=0;
		boolean[][] isp=new boolean[N][N];
		for(i=0;i<N;i++){
			for(j=0;j<N;j++)
				isp[i][j]=false;
		}
		for(i=1;i<N;i++){
			int l=i-p[i]+1,r=i+p[i]-1;
			if(l>=0 && r<N){
				while(l<=r){
					isp[l][r]=true;
					l++;
					r--;
				}
			}
		}
		dp[0]=0;
		for(i=1;i<n;i++){
			dp[i]=dp[i-1]+1;
			for(j=0;j<i;j++){
				if(j==0 && p[i+1]>i+1){
					dp[i]=0;
				}
				else if(j>0 && p[i+j+1]>i-j+1){
					if(dp[i]>dp[j-1]+1)
						dp[i]=dp[j-1]+1;
				}
			}
		}
		for(i=0;i<n;i++)
			System.out.println(dp[i]);
        return dp[n-1];
    }
	
	/*
	 * ������ǽ���ʧ���Ѿõ�O(N)������ִ����㷨����������ı�������iΪ���Ľ�㣬����ż���۵ķ���ϸ��
	 * �����ǣ���ÿ���ַ�֮������Ը���#���ָ��
	 *  w a a b w s w f d
	 * #w#a#a#b#w#s#w#f#d#
	 * p[i]��ʾ��iΪ���ĵ�ʱ�����Ļ����ִ����ȣ�����p[i]-1��Ϊ��Ļ����ִ�
	 */
	public int[] maxPalindrome(String s){
		StringBuilder sb=new StringBuilder();
		int n=s.length();
		int i,j;
		for(i=0;i<s.length();i++){
			sb.append("#");
			sb.append(s.charAt(i));
		}
		sb.append("#");
		String ss=sb.toString();
		int N=2*n+1;
		int[] p=new int[N];
		/*
		 * mx��ʾ��ǰ���ĳ�������ַ��±�
		 * index��ʾ�ַ���ʱ�����Ľ��
		 * i,j�ǹ���index�ԳƵĽ��
		 * i+j=2*index
		 * 
		 */
		
		int mx=0;
		int index=0;
		p[0]=1;
		int cnt=0;
		for(i=1;i<N;i++){
			/*
			 * 2*index-i��i����index�ԳƵĽ��
			 * ��Ϊ��i>index�������ҵ���ĶԳƵ㣬2*index-i,��ʱp[2*index-i]���Ѿ��������Ļ�����ģ���������
			 * mx-i���볤��Ϊp[2*index-i]��ߵĴ���С��0
			 */
			if(mx>i){
				p[i]=mx-i>p[2*index-i]?p[2*index-i]:mx-i;
			}
			else{
				p[i]=1;
			}
			for(;i+p[i]<N && i-p[i]>=0 && ss.charAt(i+p[i])==ss.charAt(i-p[i]);p[i]++);
			
			if(p[i]+i>mx){
				mx=p[i]+i;
				index=i;
			}
		}
		int ans=0;
		int[] dp=new int[N];
		return dp;
	}
	public boolean isPalindrome(String s){
		int n=s.length();
		for(int i=0;i<n/2;i++){
			if(s.charAt(i)!=s.charAt(n-i-1))	
				return false;
		}
		return true;
	}
	public static void main(String[] args){
		Candy and=new Candy();
		
		String s="aab";
		and.minCut(s);
	}
}
